﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    //http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
    public class Node
    {
        public Node Left { get; set; }
        public Node Right { get; set; }

        public int Min { get; set; }
        public int Max { get; set; }

        public int Value { get; set; }

        public int Index { get; set; }
    }

    public class RQM
    {
        private readonly Node _root;
        public Node Root { get { return _root; } }

        public RQM(int[] arr)
        {
            List<int> list = new List<int>(arr);
            list.Add(0);
            _root = ConstructTree(list.ToArray(), 0, list.Count - 1);
        }

        public Node QueryMin(int start, int end)
        {
            var root = _root;
            return QueryMinRecursive(root, start, end);
        }

        private Node QueryMinRecursive(Node root, int start, int end)
        {
            if (root.Max < start || root.Min > end)
            {
                return new Node { Value = int.MaxValue };
            }
            if (start <= root.Min && end >= root.Max)
            {
                return root;
            }

            Node left = QueryMinRecursive(root.Left, start, end);
            Node right = QueryMinRecursive(root.Right, start, end);

            return left.Value < right.Value ? left : right;
        }

        private Node ConstructTree(int[] arr, int start, int end)
        {
            Node root = new Node { Min = start, Max = end };

            if (start == end)
            {
                root.Value = arr[start];
                root.Index = start;
                return root;
            }

            if (end - start == 1)
            {
                root.Left = new Node { Min = start, Max = start, Index = start, Value = arr[start] };
                root.Right = new Node { Min = end, Max = end, Index = end, Value = arr[end] };
            }
            else
            {
                int middle = (start + end) / 2;

                root.Left = ConstructTree(arr, start, middle);
                root.Right = ConstructTree(arr, middle + 1, end);
            }

            Node minNode = root.Left.Value < root.Right.Value ? root.Left : root.Right;
            root.Value = minNode.Value;
            root.Index = minNode.Index;

            return root;
        }
    }
}
